package com.zhouhong;

/**
 * @ClassName: array
 * @Description: 二次封装自己的数组类
 * @Author: zhouhong
 * @Create: 2021-03-29 15:47
 **/
public  class Array<E> {

    private E[] data;
    private int size;
    // 构造函数，传入数组的容量 capacity 构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }
    // 无参构造函数，默认数组的容量 capacity = 10
    public Array(){
        this(10);
    }
    // 获取数组实际长度
    public int getSize(){
        return size;
    }
    // 获取容量
    public int getCapacity(){
        return data.length;
    }
    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }
    // 数组最后添加 O(n)
    public void addLast(E e){
        add(size, e);
    }
    // 向数组头部添加元素 O(1)
    public void addFirst(E e){
        add(0, e);
    }
    // 获取某个位置上的元素 O(1)
    public E get(int index){
        if (index < 0 || index > size){
            throw new IllegalArgumentException("index必须大于等于0 ，并且小于等于数组长度size");
        }
        return data[index];
    }
    // 更新元素 O(1)
    void set(int index, E e){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("index必须大于等于0 ，并且小于等于数组长度size");
        }
        data[index] = e;
    }
    // 向指定位置添加元素 O(n)
    public void add(int index, E e){
        if (index < 0 || index > size){
            throw new IllegalArgumentException("index必须大于等于0 ，并且小于等于数组长度size");
        }
        // 数组已满：扩容
        if (size == data.length){
            // 扩容 2 倍
            resize(data.length * 2);
        }
        for (int i = size - 1; i >= index ; i--) {
            data[i + 1] = data[i];
        }
        data[index] = e;
        size ++;
    }

    // 查找数组中是否有元素e O(n)
    public boolean contains(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)){
                return true;
            }
        }
        return false;
    }
    // 查找某个元素对应的索引(重复元素只返回一个索引) O(n)
    public int find(E e){
        for (int i = 0; i < size; i++) {
            if (data[i].equals(e)){
                return i;
            }
        }
        return -1;
    }
    // 删除某个指定索引上的元素(直接覆盖、前移),返回删除的元素 O(n)
    public E  remove(int index){
        if (index < 0 || index >= size){
            throw new IllegalArgumentException("index必须大于等于0 ，并且小于等于数组长度size");
        }
        E result = data[index];
        for (int i = index; i < size; i++) {
            data[i] = data[i + 1];
        }
        size --;
        data[size] = null;
        // 当长度小于容量的 1/2 把容量自动缩小为原来长度的 1/2
        // 懒加载，当为1/4时缩容
        if (size == data.length >> 2 && data.length >> 1 != 0){
            resize(data.length / 2);
        }

        return result;
    }
    // 删除第一个元素 O(n)
    public E removeFirst(){
        return remove(0);
    }
    // 删除最后一个元素 O(1)
    public E removeLast(){
        return remove(size - 1);
    }
    // 如果数组中有某个元素，就删除(相同元素，只删除一个)
    public void removeElenent(E e){
        int index = find(e);
        if (index != -1){
            remove(index);
        }
    }

    // 扩容
    private void resize(int newCapacity){
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    public E getLast(){
        return get(size - 1);
    }
    public E getFirst(){
        return get(0);
    }

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        result.append('[');
        for (int i = 0; i < size; i++) {
            result.append(data[i]);
            if (i != size - 1){
                result.append(", ");
            }
        }
        result.append(']');
        return result.toString();
    }
}
